package B刷题.排序;

/**
 * @author wei.zhao
 * @description: 1710.卡车上的最大单元数
 * @date 2022年11月15日 14:19
 */
public class Code05_MaximumUnits {

    /**
     * 按照箱子可以装载的单元数排序，从大往下取
     */
    public int maximumUnits(int[][] boxTypes, int truckSize) {
        int result = 0;
        if (boxTypes.length == 0) {
            return result;
        }
        // 按照每个箱子可以装载的单元数排序
        sort(boxTypes);
        // 剩余的箱子空间
        int leftTruckSize = truckSize;
        // 当前到的箱子种类索引位
        int i = 0;
        while (leftTruckSize > 0 && i < boxTypes.length) {
            if (leftTruckSize > boxTypes[i][0]) {
                result += boxTypes[i][0] * boxTypes[i][1];
                leftTruckSize -= boxTypes[i][0];
                i++;
            } else {
                result += leftTruckSize * boxTypes[i][1];
                leftTruckSize = 0;
            }
        }
        return result;
    }

    private void sort(int[][] boxTypes) {
        for (int i = 0; i < boxTypes.length; i++) {
            int max = i;
            for (int i1 = i; i1 < boxTypes.length; i1++) {
                if (boxTypes[i1][1] > boxTypes[max][1]) {
                    max = i1;
                }
            }
            swap(boxTypes, i, max);
        }
    }

    private void swap(int[][] boxTypes, int i, int max) {
        int[] temp = boxTypes[i];
        boxTypes[i] = boxTypes[max];
        boxTypes[max] = temp;
    }

}
